package com.example.demo.test;

import lombok.Data;

/**
 * @author墨尘
 * @date 2021/12/21
 * @ApiNote
 * 红黑树
 */
@Data
public class RBTree<K extends Comparable<K> , V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    /**
     * 树根的引用
     */
    private RBNode root;


    /**
     * 获取当前节点的父节点
     * @param rbNode
     */
    private RBNode parentOf(RBNode rbNode){
        if (rbNode != null){
            return (rbNode);
        }
        return null;
    }

    /**
     * 节点是否为红色
     * @param boolean
     */
    private boolean isRed(RBNode node){
        if (node != null){
            return RED == node.color;
        }
        return false;
    }
    /**
     * 节点是否为红色
     * @param boolean
     */
    private boolean isBlack(RBNode node){
        if (node != null){
            return BLACK == node.color;
        }
        return false;
    }


    /**
     * 设置节点为红色
     * @param node
     */
    private void setRed(RBNode node){
        if (null != node){
            node.color = RED;
        }
    }
    /**
     * 设置节点为黑色
     * @param node
     */
    private void setBlack(RBNode node){
        if (null != node){
            node.color = BLACK;
        }
    }

    /**
     * 中序打印二叉树
     */
    private void inOrderPrint(){
        inOrderPrint(this.root);
    }
    private void inOrderPrint(RBNode node){
        if (null != node){
            inOrderPrint(node.left);
            System.out.println("key:"+node.k+"value:"+node.v);
            inOrderPrint(node.rigth);
        }
    }

    /**
     * 左旋
     * @param
     */
    private void leftRotate(RBNode x){
            RBNode y = x.rigth;
            //将x的右子节点指向y的左子节点，将Y的左子节点的父节点更新为X
            x.rigth = y.left;
            if (y.left != null){
                y.left.parent = x;
            }
            //当X的父节点，更新为Y的父节点为X的父节点，并将X的父节点指定子树（当前X的子树位置）指定为Y
            if (x.parent != null){
                y.parent = x.parent;
                if (x == x.parent.left){
                    x.parent.left = y;
                }else {
                    x.parent.rigth = y;
                }
            }else {
                //说明X为根节点
                this.root = y;
                this.root.parent = null;
            }
            //将X的父节点更新为Y，将Y的 左子节点更新为X
            x.parent = y;
            y.left = x;
    }

    /**
     *右旋
     * 1、将Y的左子节点指向X的右子节点，并且更新X的右子节点的父节点为Y
     * 2、当Y的父节点不为空时，更新X的父节点为Y的父节点，更新Y的父节点的指定子节点（Y当前的位置为X）
     * ３、更新Y的父节点为X，更新X的右子节点为Y
     */
    private void rightRotate(RBNode y){
        RBNode x = y.left;
        //1、将Y的左子节点指向X的右子节点，并且更新X的右子节点的父节点为Y
        y.left = x.rigth;
        if (x.rigth != null){
            x.rigth.parent = y;
        }
        //2、当Y的父节点不为空时，更新X的父节点为Y的父节点，更新Y的父节点的指定子节点（Y当前的位置为X）
        if (y.parent != null){
            x.parent = y.parent;
            if (y == y.parent.left){
                y.parent.left = x;
            }else {
                y.parent.rigth = x;
            }
        }else {
            this.root = x;
            this.root.parent = null;
        }
        //３、更新Y的父节点为X，更新X的右子节点为Y
        y.parent = x;
        x.rigth = y;
    }

    /**
     * 公开的插入方法
     * Key
     * Value
     */
    public void insert(K key, V value){
        RBNode rbNode = new RBNode();
        rbNode.setK(key);
        rbNode.setV(value);
        //新节点一定是红色
        rbNode.setColor(RED);
        insert(rbNode);
    }

    private void insert(RBNode node){
        //第一步：查找当前node父节点
        RBNode parent = null;
        RBNode x = this.root;
        while (x != null){
            parent = x;
            //cmp>0说明node.key大于X.key，需要到X的右子树查找
            //cmp == 0  说明node.key 等于x.key 说明需要进行替换操作
            //cmp<0说明node.key小于X.key，需要到X的左子树查找
            int cmp = node.k.compareTo(x.k);
            if (cmp > 0){
                x = x.rigth;
            }else if (cmp == 0){
                x.setV(node.getV());
                return;
            }else if (cmp < 0){
                x = x.left;
            }
        }
        node.parent = parent;
        if (parent != null){
            //判断node与parent的K谁大
            int cmp = node.k.compareTo(parent.k);
            if (cmp > 0){
                //当前node的K比parent的K大，需要吧Node放入parent的右子节点
                parent.rigth = node;
            }else {
                //当前node 的K比Parent的K小，需要吧Node放入parent的左子节点
                parent.left = node;
            }
        }else {
            this.root = node;
        }
        //需要调用修复红黑树平衡方法
        insertFixUp(node);
    }


    /**
     *插入后修复红黑树平衡方法
     *  情景1：红黑树为空树，　　　将根节点染色为黑色
     *  情景2：插入节点的Key已经存在　不需要处理
     *  情景3：插入节点的父节点为黑色　因为所插入的路径，黑色节点没有变化，所以红黑树依然平衡，不需要处理
     *  情景4：需要处理
     *      情景4：插入节点的父节点为红色
     *          情景4.1：叔叔节点存在，并且为红色（父-叔 双红）　将爸爸和叔叔染色为黑色，将爷爷染色为红色，在爷爷节点为当前节点，进行下一步处理
     *          情景4.2：叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
     *              情景4.2.1：插入节点为父节点的左子节点（LL情况）　将爸爸染色为黑色，将爷爷染色为红色，以爷爷节点右旋
     *              情景4.2.2：插入节点为其父节点的右子节点（LR情况）    以爸爸节点进行一次左旋，得到4.2.1的情景，然后指定爸爸节点为当前节点，进行下一轮处理
     *          情景４.３：叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
     *              情景４.３.１：插入节点为其父节点的右子节点（RR情况）　将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点进行左旋
     *              情景４.３.２：插入节点为其父节点的左子节点（RL情况）    以爸爸节点进行一次右选，得到4.3.1情景，然后指定爸爸节点为当前节点，进行下一轮处理
     */
    private  void insertFixUp(RBNode node){
        this.root.setColor(BLACK);

        RBNode parent = parentOf(node);
        RBNode gpraent = parentOf(parent);
        // 情景4：插入节点的父节点为红色
        if (parent != null && isRed(parent)){
            //如果父节点为红色，那么一定存在爷爷节点
            RBNode uncle = null;
            if (parent == gpraent.left){
                uncle = gpraent.rigth;
                //情景4.1：叔叔节点存在，并且为红色（父-叔 双红）
                if (uncle != null && isRed(uncle)){
                    //将爸爸和叔叔染色为黑色，将爷爷染色为红色，在爷爷节点为当前节点，进行下一步处理
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gpraent);
                    insertFixUp(gpraent);
                    return;
                }
                //情景4.2：叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
                    if (uncle == null || isBlack(uncle)){
                        //情景4.2.1：插入节点为父节点的左子节点（LL情况）　将爸爸染色为黑色，将爷爷染色为红色，以爷爷节点右旋
                        if (node == parent.left){
                            setBlack(parent);
                            setRed(gpraent);
                            rightRotate(gpraent);
                            return;
                        }
                        //情景4.2.2：插入节点为其父节点的右子节点（LR情况）    以爸爸节点进行一次左旋，得到4.2.1的情景，然后指定爸爸节点为当前节点，进行下一轮处理
                        if (node == parent.rigth){
                            leftRotate(parent);
                            insertFixUp(parent);
                            return;
                        }
                    }
            }else {
                uncle = gpraent.left;
                //父节点为爷爷节点的右子树
                //情景4.1：叔叔节点存在，并且为红色（父-叔 双红）
                if (uncle != null && isRed(uncle)){
                    //将爸爸和叔叔染色为黑色，将爷爷染色为红色，在爷爷节点为当前节点，进行下一步处理
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gpraent);
                    insertFixUp(gpraent);
                    return;
                }
                //情景４.３：叔叔节点不存在，或者为黑色
                if (uncle == null || isBlack(uncle)){
                    //情景４.３.１：插入节点为其父节点的右子节点（RR情况）　将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点进行左旋
                    if (node == parent.rigth){
                        setBlack(parent);
                        setRed(gpraent);
                        leftRotate(gpraent);
                        return;
                    }
                    //情景４.３.２：插入节点为其父节点的左子节点（RL情况）    以爸爸节点进行一次右选，得到4.3.1情景，然后指定爸爸节点为当前节点，进行下一轮处理
                    if (node == parent.left){
                        rightRotate(parent);
                        insertFixUp(parent);
                        return;
                    }
                }
            }
        }
    }


    @Data
    public static class RBNode<K extends Comparable<K> , V> {
        private RBNode parent;
        private RBNode left;
        private RBNode rigth;
        private boolean color;
        private K k;
        private V v;
    }

}
